A microprocessor is a digital device that executes instructions specified by a computer program. Modern microprocessors employ an internal call/return stack to reduce pipeline bubbles introduced by lengthy memory accesses associated with call and return instructions.
A call instruction comprises an instruction that changes the flow of a program to a subroutine, whose address is specified in the call instruction. When a call instruction is executed, the return address, i.e., the address of the instruction after the call instruction, is pushed onto a stack in main memory pointed to by a stack pointer register in the microprocessor, and the address of the subroutine is loaded into the instruction pointer register of the microprocessor. A return instruction comprises an instruction that changes the flow of a program from the subroutine back to the instruction following the call instruction in the program. When a return instruction is executed, the return address previously pushed onto the stack is popped from the main memory stack and loaded into the instruction pointer register.
In a microprocessor that incorporates a call/return stack, when a call instruction executes, the return address is pushed onto the call/return stack to enable instruction fetching to continue, and later stages of the pipeline subsequently update the main memory stack with the return address. Conversely, when a return instruction executes, the return address is popped from the call/return stack to enable instruction fetching to continue, without having to wait for the relatively lengthy retrieval of the return address from the main memory stack.
The effectiveness of a call/return stack is largely determined by the ability of the processor to keep the call/return stack consistent with main memory. Inconsistencies between the main memory and the call/return stack may be introduced by speculative updates of the call/return stack in response to call or return instructions. An update of the call/return stack may be speculative because an instruction ahead of the call/return in the pipeline causes an invalidating event, such as generating an exception, for example, which requires the pipeline to flush all the instructions behind the exception-causing instruction, including speculatively executed call/return instructions. Similarly, a branch instruction executing ahead of call/return instructions may have been mispredicted, which might require the pipeline to flush the speculatively executed call/return instructions. Because the call/return stack has been speculatively updated in response to the call/return instructions, but the main memory stack has not yet been updated until the call/return instructions are no longer speculative, the contents of the call/return stack and the contents of the main memory stack are inconsistent.
U.S. Pat. No. 6,314,514, entitled METHOD AND APPARATUS FOR CORRECTING AN INTERNAL CALL/RETURN STACK IN A MICROPROCESSOR THAT SPECULATIVELY EXECUTES CALL AND RETURN INSTRUCTIONS, which is incorporated by reference herein, describes a method and apparatus for keeping a call/return stack consistent with main memory in spite of speculative call/return instruction executions. However, the apparatus described in the Patent operates in a microprocessor in which a branch instruction misprediction is detected from only a single stage in the microprocessor pipeline, and will not operate effectively in a microprocessor that takes exceptions or detects branch instruction mispredictions from multiple stages of the pipeline.
Therefore, what is needed is a method and apparatus for correcting an internal call/return stack in a microprocessor that detects incorrect speculative execution of call/return instructions from multiple pipeline stages.